package com.fr.lintcode;

import java.util.Stack;

import org.junit.Test;

/**
*作者：furong
*日期：2017年3月6日
*时间：下午6:03:16
*/
public class Q207 {
    class Solution {

        /**
         * @param A: An integer array
         */
        Interval root = null;

        public Solution(int[] A) {
            if (A == null || A.length == 0) {
                return;
            }
            root = buildInterval(0, A.length - 1);
            calculate(root, A);
        }

        private long calculate(Interval node, int[] a) {
            if (node == null) {
                return 0;
            } else if (node.start == node.end) {
                node.sum = a[node.start];
                return node.sum;
            }
            long left = calculate(node.left, a);
            long right = calculate(node.right, a);
            node.sum = left + right;
            return node.sum;
        }

        private Interval buildInterval(int start, int end) {
            Interval node = new Interval(start, end);
            if (start < end) {
                int mid = (start + end) / 2;
                node.left = buildInterval(start, mid);
                node.right = buildInterval(mid + 1, end);
            }
            return node;
        }

        /**
         * @param start, end: Indices
         * @return: The sum from start to end
         */
        public long query(int start, int end) {
            return query(root, start, end);
        }

        private long query(Interval node, int start, int end) {
            if (node == null) {
                return 0;
            }
            if (node.start == start && node.end == end) {
                return node.sum;
            }
            int mid = (node.start + node.end) / 2;
            if (mid < start) {
                return query(node.right, start, end);
            } else if (mid >= end) {
                return query(node.left, start, end);
            }
            long left = query(node.left, start, mid);
            long right = query(node.right, mid + 1, end);
            return left + right;
        }

        /**
         * @param index, value: modify A[index] to value.
         */
        public void modify(int index, int value) {
            Stack<Interval> stack = new Stack<>();
            Interval tmp = root;
            while (tmp != null) {
                if (tmp.start == tmp.end && tmp.start == index) {
                    tmp.sum = value;
                    break;
                } else {
                    stack.add(tmp);
                    int mid = (tmp.start + tmp.end) / 2;
                    if (mid < index) {
                        tmp = tmp.right;
                    } else {
                        tmp = tmp.left;
                    }
                }
            }
            while (!stack.isEmpty()) {
                Interval i = stack.pop();
                i.sum = (i.left == null ? 0 : i.left.sum) + (i.right == null ? 0 : i.right.sum);
            }
        }
    }

    class Interval {
        int start, end;
        long sum;
        Interval left, right;

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    @Test
    public void testA() {
        // [1,2,7,8,5], [query(0,2),modify(0,4),query(0,1),modify(2,1),query(2,4)]
        int[] A = { 1, 2, 7, 8, 5 };
        Solution s = new Solution(A);
        System.out.println(s.query(0, 2));
        s.modify(0, 4);
        System.out.println(s.query(0, 1));
        s.modify(2, 1);
        System.out.println(s.query(2, 4));
    }
}
